import java.util.concurrent.ForkJoinPool;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-10-01
 * Time: 17:11
 */

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode() {}
     TreeNode(int val) { this.val = val; }
     TreeNode(int val, TreeNode left, TreeNode right) {
         this.val = val;
         this.left = left;
         this.right = right;
     }
}

//根据前序和中序还原一棵树
public class Solution {
    public int i;
    public TreeNode build(int[] preorder, int[] inorder,int iBegin,int iEnd) {
        if(iBegin>iEnd){
            return null;
        }
        int index=-1;
        //如果传来时已经减去1了,需要有=
        for (int j = iBegin; j <= iEnd; j++) {
            if(inorder[j]==preorder[i]){
                index=j;
                break;
            }
        }
        //放在i++前
        //根
        TreeNode root=new TreeNode(preorder[i]);
        i++;
        /*
        如果是根据后序和中序创建树的先右树后左树
        必须先创建右区间因为后序先找到右树的根,进入右区间后i也会--
        如果先左区间会直接找不到根
        */

        //从左区间创建左树
        TreeNode left=build(preorder,inorder,iBegin,index-1);
        //从右区间创建右树
        TreeNode right=build(preorder,inorder,index+1,iEnd);
        root.left=left;
        root.right=right;
        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int size=inorder.length-1;
        TreeNode root=build(preorder,inorder,0,size);
        return root;
    }
}
